#include "LinkedList.h"
#include <stdio.h>
#include <stdlib.h>

list *create_sort_list()
{
    Datatype d;
    node *pnew = NULL;
    list *head = (list *)malloc(sizeof(*head));
    head->nodenum = 0;
    head->first = NULL;
    head->last = NULL;
    while(1)
    {
        scanf("%d",&d);
        if(d == 0)
        {
            break;
        }
        pnew = (node *)malloc(sizeof(*pnew));
        pnew->data = d;
        pnew->next = NULL;
        pnew->prev = NULL;
        if(head->first == NULL)
        {
            head->first = pnew;
            head->last = pnew;
        }
        else
        {
            node *p = head->first;
            while(p)
            {
                if(p->data > pnew->data)
                {
                    break;
                }
                p = p->next;
            }
            if(p)
            {
                if(p == head->first)
                {
                    pnew->next = head->first;
                    head->first->prev = pnew;
                    head->first = pnew;
                }
                else
                {
                    pnew->next = p;
                    pnew->prev = p->prev;
                    p->prev->next = pnew;
                    p->prev = pnew;
                }
            }
            else
            {
                head->last->next = pnew;
                pnew->prev = head->last;
                head->last = pnew;
            }
        }
        head->nodenum++;
    }
    return head;
}

list *same(list *A,list *B)
{
    list *C = (list *)malloc(sizeof(*C));
    C->nodenum = 0;
    C->first = NULL;
    C->last = NULL;
    node *pa = A->first;
    node *pb = B->first;
    while(pa)
    {
        pb = B->first;//重置pb指针
        while(pb)
        {
            if(pa->data == pb->data)
            {
                node *p = (node *)malloc(sizeof(*p));
                p->data = pa->data;
                p->next = NULL;
                p->prev = NULL;
                if(C->first == NULL)
                {
                    C->first = p;
                    C->last = p;
                }
                else
                {
                    C->last->next = p;
                    p->prev = C->last;
                    C->last = p;
                }
                C->nodenum++;
            }
            pb = pb->next;
        }
        pa = pa->next;
    }
    return C; 
}

void print_list(list *s)
{
    if(s)
    {
        node *p = s->first;
        while(p)
        {
            printf("%d ",p->data);
            p = p->next;
        }
        putchar('\n');
    }
}
